#include<iostream>
#include<vector>
using namespace std;

int tribonacci(int n) {
    if (n == 0) return 0;
    if (n == 1 || n == 2) return 1;
    vector<int> dp(n + 1);
    dp[0] = 0, dp[1] = dp[2] = 1;
    for (int i = 3; i <= n; i++)
    {
        dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
    }
    return dp[n];
}

int waysToStep(int n) {
    /*vector<long long> dp(n);
    if (n == 1) return 1;
    if (n == 2) return 2;
    if (n == 3) return 4;
    dp[0] = 1, dp[1] = 2, dp[2] = 4;
    for (int i = 3; i < n; i++)
    {
        dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 3]) % 1000000007;
    }
    return dp[n - 1] % 1000000007;*/

    if (n == 1) return 1;
    if (n == 2) return 2;
    if (n == 3) return 4;
    long long a = 1, b = 2, c = 4, d = 0;
    for (int i = 3; i < n; i++)
    {
        d = (a + b + c) % 1000000007;
        a = b, b = c, c = d;
    }
    return d;

}

int main()
{
    tribonacci(4);
    waysToStep(61);
	return 0;
}